Sensor Placement for Optimal Kalman Filtering: Fundamental Limits, Submodularity, and Algorithms

摘要

In this paper, we focus on sensor placement in linear dynamic estimation,where the objective is to place a small number of sensors in a system ofinterdependent states so to design an estimator with a desired estimationperformance. In particular, we consider a linear time-variant system that iscorrupted with process and measurement noise, and study how the selection ofits sensors affects the estimation error of the corresponding Kalman filterover a finite observation interval. Our contributions are threefold: First, weprove that the minimum mean square error of the Kalman filter decreases onlylinearly as the number of sensors increases. That is, adding extra sensors soto reduce this estimation error is ineffective, a fundamental design limit.Similarly, we prove that the number of sensors grows linearly with the system'ssize for fixed minimum mean square error and number of output measurements overan observation interval; this is another fundamental limit, especially forsystems where the system's size is large. Second, we prove that the logdet ofthe error covariance of the Kalman filter, which captures the volume of thecorresponding confidence ellipsoid, with respect to the system's initialcondition and process noise is a supermodular and non-increasing set functionin the choice of the sensor set. Therefore, it exhibits the diminishing returnsproperty. Third, we provide efficient approximation algorithms that select asmall number sensors so to optimize the Kalman filter with respect to thisestimation error ---the worst-case performance guarantees of these algorithmsare provided as well. Finally, we illustrate the efficiency of our algorithmsusing the problem of surface-based monitoring of CO2 sequestration sitesstudied in Weimer et al. (2008).